"""
得到一个数组的所有组合,
可以换个说话： 得到一个数组元素为n的集合，

这样我们可以得到元素为1，元素为2，元素为3...元素为n的所有集合


"""
from typing import List


def combination(l: List):
    ans = []
    n = len(l)

    def helper(array, start, count):
        # print(array)
        if count == 0:
            ans.append(array)
            return
        for i in range(start, n - count + 1):
            # 为啥要 - count + 1 呢，因为如果长度为3，元素为3那么只要运行1次，长度为4，元素为3只要运行2次，后面的元素长度不够
            helper(array + [l[i]], i + 1, count - 1)

    for i in range(1, n + 1):
        helper([], 0, i)
    return ans


def test():
    assert combination([1, 2, 3, 4, 5]) == [
        [1],
        [2],
        [3],
        [4],
        [5],
        [1, 2],
        [1, 3],
        [1, 4],
        [1, 5],
        [2, 3],
        [2, 4],
        [2, 5],
        [3, 4],
        [3, 5],
        [4, 5],
        [1, 2, 3],
        [1, 2, 4],
        [1, 2, 5],
        [1, 3, 4],
        [1, 3, 5],
        [1, 4, 5],
        [2, 3, 4],
        [2, 3, 5],
        [2, 4, 5],
        [3, 4, 5],
        [1, 2, 3, 4],
        [1, 2, 3, 5],
        [1, 2, 4, 5],
        [1, 3, 4, 5],
        [2, 3, 4, 5],
        [1, 2, 3, 4, 5],
    ]


if __name__ == "__main__":
    combination([1, 2, 3, 4, 5])
